import java.util.*;

class Solution {
    public static List<String> topKFrequent(String[] words, int k) {
        //1.需要统计每个单词出现的次数
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.get(word) == null) {
                map.put(word, 1);
            } else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }
        //2.通过上述代码，我们已经得到了每个单词出现的次数，存储到了map中
        //看哪个单词出现的频率，接下了要遍历的是map
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());//根据key变成大根堆
                }
                //默认根据频率来创建小根堆
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        //3.遍历map，把每个单词及频率获取到，存放到小根堆当中，以TOPK的问题去解决
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                //此时堆放满了，需要每次和堆顶元素进行比较
                Map.Entry<String, Integer> top = minHeap.peek();
                //频率相同
                if (top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        //出堆
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    //频率不相同
                    if (entry.getValue().compareTo(top.getValue()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> temp = minHeap.poll();
            ret.add(temp.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}